public class Test {
    public static void main(String [] args){
        //顺序输出123的每一位。
        //如果数字是一位数，就直接输出就好
        //也就是数字小于10，就可以 0-9；
        //print(12365);
        //System.out.println(sumN(5));
        //System.out.println(fib(40));
        //System.out.println(fib2(41));
    }
    //我们用循环实现，这样代码的速度会变得快得很——
    //时间复杂度是o(n)
    //迭代其实就是循环，迭代高大上而已
    public static int fib2(int n){
        int x = 0;
        int y = 1;
        if(n==1){
            return x;
        }else if(n==2){
            return y;
        }else{
            for(int i=3;i<=n;i++){
                //此处有多个实现方式
                int tmp = x;
                x = y;
                y = tmp + x;
            }
            return y;
        }
    }

    //如果面试官，让你写斐波那契的代码，一定不要写递归实现的
    //这个重复是极为恐怖的，当你给的数字很大很大的时候，就非常恐怖了
    //时间复杂度非常高。

    //

    //斐波那契数列的第n项
    // 0 1 1 2 3 5 8
    //定义是包含0的_所以我们写了从零开始的斐波那契数

    public static int fib(int n){
        if(n==1){
            return 0;
        }else if(n==2){
            return 1;
        }else{
            return fib(n-1)+fib(n-2);
        }
    }

    public static void print(int n){
        if(n<10){
            System.out.println(n);
        }else{
            print(n/10);
            System.out.println(n % 10);
        }
    }
    //1+2+3+4+……+10
    //n+sum(n-1);
    public static int sumN(int n){
        if(n==1){
            return 1;
        }else{
            int tmp = n + sumN(n-1);
            return tmp;
        }
    }

    //求一个数的每一位的和
    //
    public static int func(int n){
        if(n<10){
            return 10;
        }else{
            int tmp=func(n/10)+n%10;
            return tmp;
        }
    }


}
